Add Binary
Given two binary strings a and b, return their sum as a binary string.
Example 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
Constraints:
1 <= a.length, b.length <= 10^4
a and b consist only of '0' or '1' characters.
Each string does not contain leading zeros except for the zero itself.
My Solution
To solve this efficiently in Java we need to use the StringBuilder class since it updates strings in place. We start at the end of both strings and add the integer representation of the corresponding characters. We keep track of a carry digit and add this at each iteration. The character we add to our StringBuilder output would be (out % 2) and we update the carry to be (out / 2). Once we have exhausted all the characters in one of the strings, we add all the characters of the other string with the carry to our output. Finally if the carry bit is 1, we add that to the output string. Now the output string is reversed so we just need to reverse the StringBuilder and convert it to a String and return it.
Time complexity would be O(m+n), where m is the length of a and n is the length of b. It is only linear time because StringBuilder updates strings in place. Space complexity would be O(1) because we don’t need any additional space other than for the output string.
class Solution {
public String addBinary(String a, String b) {
StringBuilder sb = new StringBuilder();
int m = a.length();
int n = b.length();
int i = m-1;
int j = n-1;
int carry = 0;
while (i >= 0 && j >= 0) {
int num1 = a.charAt(i) - '0';
int num2 = b.charAt(j) - '0';
int out = num1 + num2 + carry;
sb.append((char)('0' + (out % 2)));
carry = out / 2;
i--;
j--;
}
while (i >= 0) {
int num = a.charAt(i) - '0';
int out = num + carry;
sb.append((char) ('0' + (out % 2)));
carry = out / 2;
i--;
}
while (j >= 0) {
int num = b.charAt(j) - '0';
int out = num + carry;
sb.append((char) ('0' + (out % 2)));
carry = out / 2;
j--;
}
if (carry > 0) {
sb.append('1');
}
return sb.reverse().toString();
}
}